{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Next Greater Element I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #hash-table #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #哈希表 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nextGreaterElement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #下一个更大元素 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><code>nums1</code>&nbsp;中数字&nbsp;<code>x</code>&nbsp;的 <strong>下一个更大元素</strong> 是指&nbsp;<code>x</code>&nbsp;在&nbsp;<code>nums2</code> 中对应位置 <strong>右侧</strong> 的 <strong>第一个</strong> 比&nbsp;<code>x</code><strong>&nbsp;</strong>大的元素。</p>\n",
    "\n",
    "<p>给你两个<strong> 没有重复元素</strong> 的数组&nbsp;<code>nums1</code> 和&nbsp;<code>nums2</code> ，下标从 <strong>0</strong> 开始计数，其中<code>nums1</code>&nbsp;是&nbsp;<code>nums2</code>&nbsp;的子集。</p>\n",
    "\n",
    "<p>对于每个 <code>0 &lt;= i &lt; nums1.length</code> ，找出满足 <code>nums1[i] == nums2[j]</code> 的下标 <code>j</code> ，并且在 <code>nums2</code> 确定 <code>nums2[j]</code> 的 <strong>下一个更大元素</strong> 。如果不存在下一个更大元素，那么本次查询的答案是 <code>-1</code> 。</p>\n",
    "\n",
    "<p>返回一个长度为&nbsp;<code>nums1.length</code> 的数组<em> </em><code>ans</code><em> </em>作为答案，满足<em> </em><code>ans[i]</code><em> </em>是如上所述的 <strong>下一个更大元素</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [4,1,2], nums2 = [1,3,4,2].\n",
    "<strong>输出：</strong>[-1,3,-1]\n",
    "<strong>解释：</strong>nums1 中每个值的下一个更大元素如下所述：\n",
    "- 4 ，用加粗斜体标识，nums2 = [1,3,<strong>4</strong>,2]。不存在下一个更大元素，所以答案是 -1 。\n",
    "- 1 ，用加粗斜体标识，nums2 = [<em><strong>1</strong></em>,3,4,2]。下一个更大元素是 3 。\n",
    "- 2 ，用加粗斜体标识，nums2 = [1,3,4,<em><strong>2</strong></em>]。不存在下一个更大元素，所以答案是 -1 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums1 = [2,4], nums2 = [1,2,3,4].\n",
    "<strong>输出：</strong>[3,-1]\n",
    "<strong>解释：</strong>nums1 中每个值的下一个更大元素如下所述：\n",
    "- 2 ，用加粗斜体标识，nums2 = [1,<em><strong>2</strong></em>,3,4]。下一个更大元素是 3 。\n",
    "- 4 ，用加粗斜体标识，nums2 = [1,2,3,<em><strong>4</strong></em>]。不存在下一个更大元素，所以答案是 -1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length &lt;= nums2.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>nums1</code>和<code>nums2</code>中所有整数 <strong>互不相同</strong></li>\n",
    "\t<li><code>nums1</code> 中的所有整数同样出现在 <code>nums2</code> 中</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以设计一个时间复杂度为 <code>O(nums1.length + nums2.length)</code> 的解决方案吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [next-greater-element-i](https://leetcode.cn/problems/next-greater-element-i/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [next-greater-element-i](https://leetcode.cn/problems/next-greater-element-i/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,1,2]\\n[1,3,4,2]', '[2,4]\\n[1,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        greater = self.next_greater(nums2)\n",
    "        greater_map = {}\n",
    "        for i in range(len(nums2)):\n",
    "            greater_map[nums2[i]] = greater[i]\n",
    "        res = [0] * len(nums1)\n",
    "        for i in range(len(nums1)):\n",
    "            res[i] = greater_map[nums1[i]]\n",
    "        return res\n",
    "    def next_greater(self, nums):\n",
    "        n = len(nums)\n",
    "        res = [0 for _ in range(n)]\n",
    "        s = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while s and s[-1] <= nums[i]:\n",
    "                s.pop()\n",
    "            res[i] = s[-1] if s else -1\n",
    "            s.append(nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        output=[]\n",
    "        for i in nums1:\n",
    "            index=nums2.index(i)\n",
    "            for j in nums2[index:]:\n",
    "                if j>i:\n",
    "                    output.append(j)\n",
    "                    break\n",
    "            else:\n",
    "                output.append(-1)\n",
    "        return output\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        dmap = {}\n",
    "        stack = []\n",
    "        for n in nums2:\n",
    "            while stack and stack[-1]<n:\n",
    "                dmap[stack.pop()] = n\n",
    "            stack.append(n)\n",
    "        return [dmap.get(n,-1) for n in nums1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res=[]\n",
    "        for i in nums1:\n",
    "            start = nums2.index(i)+1\n",
    "            if start==len(nums2):\n",
    "                res.append(-1)\n",
    "            elif start==len(nums2)-1:\n",
    "                if nums2[-1]>i:\n",
    "                    res.append(nums2[-1])\n",
    "                else:\n",
    "                    res.append(-1)\n",
    "            else:\n",
    "                flag=1\n",
    "                for j in nums2[start:]:\n",
    "                    if j>i:\n",
    "                        res.append(j)\n",
    "                        flag=0\n",
    "                        break\n",
    "                if flag:\n",
    "                    res.append(-1)\n",
    "                    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        dict = {}\n",
    "        \n",
    "        for i in nums2:\n",
    "            while len(stack) and stack[-1] < i:\n",
    "                dict[stack.pop()] = i\n",
    "            stack.append(i)    \n",
    "        for j in range(len(nums1)):\n",
    "            nums1[j] = dict.get(nums1[j],-1)\n",
    "        return nums1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        dict = {}\n",
    "        \n",
    "        for i in nums2:\n",
    "            while len(stack) and stack[-1] < i:\n",
    "                dict[stack.pop()] = i\n",
    "            stack.append(i)    \n",
    "        for j in range(len(nums1)):\n",
    "            nums1[j] = dict.get(nums1[j],-1)\n",
    "        return nums1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        for i1 in nums1:\n",
    "            # print(1,end=\" \")\n",
    "            for i2 in nums2:\n",
    "                # print(2,end=\" \")\n",
    "                if i2 == i1:\n",
    "                    # print(3,end=\" \")\n",
    "                    idx = nums2.index(i2)\n",
    "                    nums3 = nums2[idx:]\n",
    "                    for i in nums3:\n",
    "                        if i > i2:\n",
    "                            stack.append(i)\n",
    "                            break\n",
    "                    else:\n",
    "                        stack.append(-1)\n",
    "                        break\n",
    "        return stack\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1, nums2):\n",
    "        \"\"\"\n",
    "        :type nums1: List[int]\n",
    "        :type nums2: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        for i1 in nums1:\n",
    "            # print(1,end=\" \")\n",
    "            for i2 in nums2:\n",
    "                # print(2,end=\" \")\n",
    "                if i2 == i1:\n",
    "                    # print(3,end=\" \")\n",
    "                    idx = nums2.index(i2)\n",
    "                    nums3 = nums2[idx:]\n",
    "                    for i in nums3:\n",
    "                        if i > i2:\n",
    "                            stack.append(i)\n",
    "                            break\n",
    "                    else:\n",
    "                        stack.append(-1)\n",
    "                        break\n",
    "        return stack\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1, nums2):\n",
    "        ans = []\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                if i == j:\n",
    "                    temp = nums2.index(j)\n",
    "                    break\n",
    "            flag = False\n",
    "            for t in nums2[temp + 1:]:\n",
    "                if t > i:\n",
    "                    flag = True\n",
    "                    ans.append(t)\n",
    "                    break\n",
    "            if flag == False:\n",
    "                ans.append(-1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        index, value = {}, {}\n",
    "        for i,v in enumerate(nums2):\n",
    "            index[i] = v\n",
    "            value[v] = i \n",
    "\n",
    "        for i,v in enumerate(nums1):\n",
    "            j = value[v]\n",
    "            while index.get(j+1) is not None:\n",
    "                tmp = index[j+1]\n",
    "                if tmp > v:\n",
    "                    nums1[i] = tmp\n",
    "                    break\n",
    "                j += 1\n",
    "            else:\n",
    "                nums1[i] = -1\n",
    "        \n",
    "        return nums1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        stack, hashmap = list(), dict()\n",
    "        for i in nums2:\n",
    "            while len(stack) != 0 and stack[-1] < i:\n",
    "                hashmap[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        return [hashmap.get(i, -1) for i in nums1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        dic = {}\n",
    "        l = len(nums2)\n",
    "        for i in range(l):\n",
    "            if nums2[i] not in dic:\n",
    "                dic[nums2[i]] = i\n",
    "        ans = [-1]*len(nums1)\n",
    "        l1 = len(nums1)\n",
    "        for j in range(l1):\n",
    "            index = dic[nums1[j]]\n",
    "            for i in range(index,l):\n",
    "                if nums2[i]>nums1[j]:\n",
    "                    ans[j] = nums2[i]\n",
    "                    break\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        dict1 = {}\n",
    "        stack = []\n",
    "        for i in range(len(nums2)):\n",
    "            if not stack:\n",
    "                stack.append(nums2[i])\n",
    "                continue\n",
    "            while stack and stack[-1]<nums2[i]:\n",
    "                dict1[stack.pop()] = nums2[i]\n",
    "            stack.append(nums2[i])\n",
    "        res = []\n",
    "        for num in nums1:\n",
    "            if num in dict1:\n",
    "                res.append(dict1[num])\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# intuition: \n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        book = {}\n",
    "        stack = [float('inf')]\n",
    "        res = []\n",
    "        for num in nums2:\n",
    "            while stack[-1] < num:\n",
    "                book[stack.pop()] = num\n",
    "            stack.append(num)\n",
    "        for num in nums1:\n",
    "            if num in book:\n",
    "                res.append(book[num])\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        if not nums2 or not nums1:\n",
    "            return [-1] * len(nums1)\n",
    "        stack = [nums2[0]]\n",
    "        hashMap = {}\n",
    "        i = 1\n",
    "        while i < len(nums2):\n",
    "            while stack and nums2[i] > stack[-1]:\n",
    "                hashMap[stack[-1]] = nums2[i]\n",
    "                stack.pop()\n",
    "            stack.append(nums2[i])\n",
    "            i += 1\n",
    "        while stack:\n",
    "            hashMap[stack.pop()] = -1\n",
    "        res = [hashMap[num] for num in nums1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        l=[]\n",
    "        N=len(nums1)\n",
    "        M=len(nums2)\n",
    "        for i in range(N):\n",
    "            j=0\n",
    "            while j<M:\n",
    "                if nums2[j]==nums1[i]:\n",
    "                    if j==M-1:\n",
    "                        l.append(-1)\n",
    "                        break\n",
    "                    j+=1\n",
    "                    while j<M:\n",
    "                        if nums2[j]>nums1[i]:\n",
    "                            l.append(nums2[j])\n",
    "                            break \n",
    "                        else:\n",
    "                            j+=1\n",
    "                            if j==M:\n",
    "                                l.append(-1)\n",
    "                    break\n",
    "                else:\n",
    "                    j+=1\n",
    "            \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        # l = []\n",
    "        # for i in range(len(nums1)):\n",
    "        #     for j in range(nums2.index(nums1[i])+1,len(nums2)):\n",
    "        #         if nums2[j]>nums1[i]:\n",
    "        #             l.append(nums2[j])\n",
    "        #             break\n",
    "        #         else:\n",
    "        #             l.append(-1)\n",
    "        # return l\n",
    "        res = []\n",
    "        for i in nums1:\n",
    "            for j in nums2[nums2.index(i)+1:]:\n",
    "                if j > i:\n",
    "                    res.append(j)\n",
    "                    break\n",
    "            else:\n",
    "                res.append(-1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        # d = {}\n",
    "        # stack = []\n",
    "        # for i in range(len(nums2)-1,-1,-1):\n",
    "        #     while len(stack) > 0 and stack[-1] < nums2[i]:\n",
    "        #         stack.pop()\n",
    "        #     if len(stack) == 0:\n",
    "        #         d[nums2[i]] = -1\n",
    "        #     else:\n",
    "        #         d[nums2[i]] = stack[-1]\n",
    "        #     stack.append(nums2[i])\n",
    "        #     # print(\"nums2[%d] = %d,d[nums2[%d]] = %d\"%(i,nums2[i],i,d[nums2[i]]))\n",
    "\n",
    "        # for i in range(len(nums1)-1,-1,-1):\n",
    "        #     nums1[i] = d[nums1[i]]\n",
    "        #     # print(\"nums1[i] = %d\"%(nums1[i]))\n",
    "        #     # print(\"d[nums1[i]] = %d\"%(d[nums1[i]]))\n",
    "        # return nums1\n",
    "        dic, stack = {}, []\n",
    "        for i in range(len(nums2) - 1, -1, -1):\n",
    "            while stack and stack[-1] <= nums2[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                dic[nums2[i]] = stack[-1]\n",
    "            stack.append(nums2[i])\n",
    "        return [dic.get(num, -1) for num in nums1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        res = []#初始化结果和栈\n",
    "        stack = []\n",
    "        for num in nums2:#nums2 全部入栈1\n",
    "            stack.append(num)\n",
    "        for num in nums1:#遍历子集nums1\n",
    "\n",
    "            temp = []#初始化另一个栈\n",
    "            maximum = -1 #初始化两个辅助参数（maximum 是结果， isFound 是遍历栈1停的条件）\n",
    "            isFound = False\n",
    "\n",
    "            while (len(stack) != 0 and not isFound):#遍历栈1\n",
    "                top = stack.pop()#top是栈1的栈顶元素\n",
    "                if top > num:#有可能的结果\n",
    "                    maximum = top\n",
    "                elif top == num:#结束的条件\n",
    "                    isFound = True\n",
    "                temp.append(top)\n",
    "            \n",
    "            res.append(maximum)#对于nums1中的每一个数，增加一个结果（跟着for循环变）\n",
    "\n",
    "            while (len(temp) != 0):#对于每次forloop，把temp弄回stack里（还原）\n",
    "                stack.append(temp.pop())\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        tmp = []\n",
    "        for i in nums1:\n",
    "            j = nums2.index(i)\n",
    "            isfound = False\n",
    "            while j < len(nums2)-1:\n",
    "                if nums2[j+1] > i:\n",
    "                    tmp.append(nums2[j+1])\n",
    "                    isfound = True\n",
    "                    break\n",
    "                j += 1\n",
    "            if isfound == False:\n",
    "                tmp.append(-1)\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        1. 求下一个更大大元素-> 使用单调栈\n",
    "        2. 要在nums2里面寻找，遍历nums2\n",
    "        3. 栈里只存放nums1有的元素，因为只计算nums1的下一个更大\n",
    "        4. 需要记录nums1的索引，为了保存结果\n",
    "        5. 伪代码\n",
    "        6. 代数验证伪代码正确性\n",
    "        7. 翻译伪代码\n",
    "        8. 跑测试用例\n",
    "        \"\"\"\n",
    "        res = [-1] * len(nums1)\n",
    "        stack = []\n",
    "        for num in nums2:\n",
    "            while True:\n",
    "                if stack and num > nums1[stack[-1]]:\n",
    "                    index = stack.pop()\n",
    "                    res[index] = num\n",
    "                else:\n",
    "                    break\n",
    "            if num in nums1:\n",
    "                stack.append(nums1.index(num))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        stack=collections.deque()\n",
    "        res={}\n",
    "        for i in reversed(nums2):\n",
    "            while stack and i>=stack[-1]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                res[i]=stack[-1]\n",
    "            else :\n",
    "                res[i]=-1\n",
    "            stack.append(i)\n",
    "        return [res[i] for i in nums1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        s = []\n",
    "        i = 0\n",
    "        n_map = dict()\n",
    "        while i < len(nums2):\n",
    "            while s and s[-1] < nums2[i]:\n",
    "                n_map[s.pop()] = nums2[i]\n",
    "            s.append(nums2[i])\n",
    "            i += 1\n",
    "        while s:\n",
    "            n_map[s.pop()] = -1\n",
    "        return [n_map[x] for x in nums1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        result=[]\n",
    "        stack=[]\n",
    "        for i in nums2:\n",
    "            stack.append(i)\n",
    "        for i in nums1:\n",
    "            temp=[]\n",
    "            isFound=False\n",
    "            max_=-1\n",
    "            while len(stack)!=0 and not isFound:\n",
    "                top=stack.pop()\n",
    "                if top>i:\n",
    "                    max_=top\n",
    "                elif top==i:\n",
    "                    isFound=True\n",
    "                temp.append(top)\n",
    "            result.append(max_)\n",
    "            while len(temp)!=0:\n",
    "                stack.append(temp.pop())\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        res = [-1] * len(nums1)\n",
    "        stack = [0]\n",
    "        for i in range(1,len(nums2)):\n",
    "            if nums2[i] <= nums2[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while len(stack) != 0 and nums2[i] > nums2[stack[-1]]:\n",
    "                    if nums2[stack[-1]] in nums1:\n",
    "                        index = nums1.index(nums2[stack[-1]])\n",
    "                        res[index] = nums2[i]\n",
    "                    stack.pop()\n",
    "                stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        dict1 = {}\n",
    "        for i in range(len(nums2)-1, -1, -1):\n",
    "            num = nums2[i]\n",
    "            while len(stack) != 0 and stack[-1] < num:\n",
    "                stack.pop()\n",
    "            if len(stack) == 0:\n",
    "                dict1[num] = -1\n",
    "            else:\n",
    "                dict1[num] = stack[-1]\n",
    "            stack.append(num)\n",
    "        ans = []\n",
    "        for num in nums1:\n",
    "            ans.append(dict1[num])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        n = len(nums1)\n",
    "        right = defaultdict(lambda:-1)\n",
    "        st = []\n",
    "        for x in nums2:\n",
    "            while st and st[-1]  < x:\n",
    "                right[st.pop()] = x\n",
    "            st.append(x)\n",
    "        return [right[i] for i in nums1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        l = len(nums1)\n",
    "        ans = [-1] * l\n",
    "        for i in range(l):\n",
    "            tmp = nums1[i]\n",
    "            idx = nums2.index(tmp)\n",
    "            for num in nums2[idx + 1:]:\n",
    "                if num > tmp:\n",
    "                    ans[i] = num\n",
    "                    break\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
